import org.omg.PortableInterceptor.INACTIVE;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @User: vitobo
 * @Date: 2024-06-25
 * @Description: 优先级队列学习
 *  优先级队列
 *      底层是一棵 完全二叉树
 *
 *  堆:
 *      在完全二叉树的基础上实现的, 按照层序遍历的方式存储
 *      大根堆: 根节点比左右孩子都大
 *      小根堆: 根节点比左右孩子都小
 *
 *
 *  向下调整(建大堆): 从每棵子树的根
 *
 *      1.从最后一棵子树的根节点开始进行调整  (i-1)/2 ==> (len-2)/2
 *      2.每棵子树在调整的时候, 结束的位置该如何确定
 *
 *
 *  堆, 当没有传入数组容量的时候, 默认容量是 11
 *  当没有传入比较器的时候, 它必须是可比较的
 *  优先使用的是比较器来比较
 *
 */
class Student implements Comparable<Student>{
    public int age;
    public Student(int age){
        this.age = age;
    }

    @Override
    public int compareTo(Student o) {
        return this.age - o.age;
    }
}

class IntCmp implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        //return o2-o1;
        return o2.compareTo(o1);
    }
}


public class Test {
    // 最小的前K个数据
    public static void main6(String[] args) {
        MyHeap myHeap = new MyHeap();
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        myHeap.initElem(array);
        myHeap.heapSort();
        System.out.println("----------------------");
    }
    
    public int[] smallestK(int[] arr, int k){
        Arrays.sort(arr);
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = arr[i];
        }
        return tmp;
    }

    /**
     * 时间复杂度: O(N+KlogN)
     * @param arr
     * 
     */
    public static int[] smallestK2(int[] arr, int k){
        // 1. 建立一个小根堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        // 2. 取出数组当中的每个元素,存放到小根堆当中
        for (int i = 0; i < arr.length; i++) {
            minHeap.offer(arr[i]);
        }
        
        // 3.弹出k个元素,存放到数组当中,返回即可
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = minHeap.poll();
        }
        return tmp;
    }

    /**
     * 时间复杂度: O(N*logK)
     * @param args
     */
    public static int[] smallestK3(int[] arr, int k){
        if(arr == null || k == 0){
            return new int[0];
        }
        
        // 1.建立一个大根堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new Comparator<Integer>() {

            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

        // 先将 这组数据当中的前K个元素,建立为大根堆
        // 从第k+1个元素开始, 每次和堆顶元素比较, 如果i下标的元素小于堆顶元素则出堆

        for (int i = 0; i < arr.length; i++) {
            if(minHeap.size() < k){
                minHeap.offer(arr[i]);
            }else {
                int val = minHeap.peek();
                if(val > arr[i]){
                    // 弹出大的
                    minHeap.poll();
                    // 放进小的
                    minHeap.offer(arr[i]);
                }
            }
        }

        // 将前k个最小元素赋值到数组中
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = minHeap.poll();
        }
        return tmp;
    }

    // 第K小的, 直接弹出堆顶元素
    public static int[] smallestK4(int[] arr, int k) {
        if(arr == null || k == 0) {
            return new int[0];
        }
        //1. 建立一个大根堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        //2、
        for (int i = 0; i < k; i++) {
            minHeap.offer(arr[i]);
        }

        for (int i = k; i < arr.length; i++) {
            //当前数组的元素是arr[i]    18
            int val = minHeap.peek();  //27
            if(val > arr[i]) {
                //弹出大的
                minHeap.poll();
                //放进小的
                minHeap.offer(arr[i]);
            }
        }

        //3
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = minHeap.poll();
        }
        return tmp;
    }
    
    public static void main5(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(10);
        arrayList.add(20);
        arrayList.add(6);

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(arrayList);
        System.out.println("===========");
    }

    public static void main4(String[] args) {
        // 匿名内部类, 实现了Comparator这个接口,并且重写了compare方法
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

        // lambda表达式   Java8中新增的特性
        PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>((x,y)->{return x.compareTo(y);});
        PriorityQueue<Integer> priorityQueue3 = new PriorityQueue<>((x,y)-> x.compareTo(y));

        priorityQueue.offer(10);
        priorityQueue.offer(20);
        priorityQueue.offer(6);

        System.out.println("=================");
    }

    public static void main3(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());
        priorityQueue.offer(10);
        priorityQueue.offer(20);
        priorityQueue.offer(6);

        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
    }

    public static void main2(String[] args) {
        PriorityQueue<Student> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(new Student(10));
        priorityQueue.offer(new Student(5));

        System.out.println("========================");
    }

    public static void main1(String[] args) {
        MyHeap myHeap = new MyHeap();
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        myHeap.initElem(array);
        myHeap.createHeap();
        myHeap.pop();

        System.out.println("==================");
    }

}
